package datastruct;

import java.util.ArrayList;
import java.util.Arrays;

public class FindContinuousSequence {

    /**
     * JZ41 和为S的连续正数序列
     * @param args
     */
    public static void main(String[] args) {
        FindContinuousSequence(9);
    }

    public static ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        int end = (sum + 1) / 2;
        //控制右指针
        int rk = 0;
        int windowSum = 0;
        for (int i = 1; i <= end; i++){
            //右指针右移滑动，
            while (rk < end && windowSum < sum){
                rk++;
                windowSum += rk;
            }
            if (windowSum == sum && rk - i > 0){
                ArrayList<Integer> tmp = new ArrayList<>(rk - i + 1);
                for (int k = i; k <= rk; k++){
                    tmp.add(k);
                }
                res.add(tmp);
            }
            //左指针向右滑动
            windowSum -= i;
        }
        return res;
    }
}
